#include <iostream>
using namespace std;
typedef struct node
{
    char *data;
    struct node *lchild,*rchild;
}BiNode,*BiTree;
/*先序创建二叉树*/
BiTree CreateTree(BiTree &T)
{
    char *x;
    cin>>x;
    if(*x=='#') 
        T=NULL;
    else{
        T=(BiTree)malloc(sizeof(BiNode));
        if(!T) return 0;
        T->data=x;
        CreateTree(T->lchild);
        CreateTree(T->rchild);
    }
    return T;
}
/*递归先序遍历*/
void PreOrder(BiTree &T){
    if(T!=NULL){
        cout<<T->data;
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
/*递归中序遍历*/
void InOrder(BiTree &T){
    if(T!=NULL){
        InOrder(T->lchild);
        cout<<T->data;
        InOrder(T->rchild);
    }
}
/*递归后序遍历*/
void PostOrder(BiTree &T){
    if(T!=NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        cout<<T->data;
    }
}
int main()
{
    /*  12#46###3#5###  */
    BiNode *root;//定义一个根节点
    CreateTree(root);
    PreOrder(root);
	printf(" PreOrder end...\n");
	InOrder(root);
	printf(" InOrder end...\n");
    PostOrder(root);
	printf(" PostOrder end...\n");
}